package search;

import java.util.ArrayList;
import java.util.Arrays;

public class InsertValueSearch implements MySearch {
    private int searchCount=0;

    @Override
    public int getSearchCount() {
        return searchCount;
    }

    public static void main(String[] args) {
        //int[] a = {16,52,61,61,88,124,159,561,1024,10001,200000};
        int[] a = {16,22,35,46,52,61,71,88,124,159,201,301};
        //int[] a={88,88,88,88,88,88,88,88,88,88,88,88,88};
        MySearch search = new InsertValueSearch();
        int result = search.search(a,88);
        System.out.println("查找结果:"+result);
        System.out.println("查找次数："+search.getSearchCount());
/*        int[] res = search.searchs(a,88);
        if(res==null){
            System.out.println("没有这个元素");
        }else {
            System.out.println(Arrays.toString(res));
        }*/

    }
    @Override
    public int search(int[] array, int value) {
        return insertValueSearch(array,0,array.length-1,value);
    }

    private int insertValueSearch(int[] array, int left, int right, int value) {
        if(left>right || value<array[left] || value>array[right]){
            return -1;
        }
        searchCount++;
        int mid = left+(right-left)*(value-array[left])/(array[right]-array[left]+1);
        if(value<array[mid]){
            return insertValueSearch(array,left,mid-1,value);
        }else if (value>array[mid]){
            return insertValueSearch(array,mid+1,right,value);
        }else {
            return mid;
        }
    }
    @Override
    public int[] searchs(int[] array, int value) {
        ArrayList<Integer> result = binarySearchs(array,0,array.length-1,value);
        if(result==null){
            return null;
        }
        return result.stream().mapToInt(Integer::valueOf).toArray();
    }

    private ArrayList binarySearchs(int[] array, int left, int right, int value) {
        if(left>right){
            return null;
        }
        int mid = (left+right)/2;
        if(value<array[mid]){
            return binarySearchs(array,left,mid-1,value);
        }else if (value>array[mid]){
            return binarySearchs(array,mid+1,right,value);
        }else {
            ArrayList<Integer> result = new ArrayList(array.length);
            result.add(mid);
            int i=mid-1;
            while(i>0&&array[i]==value){
                result.add(i);
                i--;
            }
            i=mid+1;
            while(i<array.length-1&&array[i]==value){
                result.add(i);
                i++;
            }
            return result;
        }
    }
}
